The Batcher-banyan network is a self-routing network which is capable of synchronously routing packets of data in time slots from a set of input terminals to a set of output terminals without centralized control. The routing through the network is determined by an address contained in the header of each packet.
The Batcher-banyan network comprises a Batcher sorting network, followed by a banyan routing network. The function of the Batcher sorting network is to arrange incoming packets in ascending or descending order according to their destination addresses. The function of the banyan network is to route the presorted packets to their destination output terminals.
The banyan network can route a data packet from any input terminal to any destination terminal, but may suffer from internal packet congestion, in the sense that two or more packets may be routed through the same internal link at the same time. However, the banyan network is internally non-blocking if in a particular time slot no more than one incoming packet is addressed to each banyan output and the packets are arranged in ascending or descending order when they arrive at the banyan inputs. Therefore it is possible to construct a non-blocking network by combining a Batcher sorting network and a banyan routing network. An example of a switching system in which a non-blocking self-routing Batcher-banyan network is utilized can be found in co-pending patent application C. M. Day, Jr. - J. N. Giacopelli - N. C. Huang - L. T. Wu, Ser. No. 021,664, entitled"Self Routing Hub Switch", filed on Mar.4, 1987 and assigned to the assignee hereof now U.S. Pat. No. 4,782,478, issued Nov. 1,1988 . The above-identified application is incorporated herein by reference.
The Batcher-banyan network may be built from small switching cells. By using VLSI technology many of these cells may be implemented in a single VLSI chip. Many applications, such as the switching system described in the above-identified patent application require the Batcher-banyan network to operate at very high speeds such as 100 megabits/sec. It is often the case that signal propagation delays in the electrical connections between individual chips comprising a network such as the Batcherbanyan network contribute more to processing delays than signal propagation delays within individual IC chips.
It has previously been suggested that"between chip signal propagation delays" in complex networks can be reduced by forming the network from chips arranged in adjoining horizontal and vertical stacks. (See, e.g. Donald K. Wilson,"Topological Aspects of Systems Partitioning", pp. 148-154, Vol. 3 "Design Theory and Practice" Proceedings of the International Conference on Design Policy Jul. 1982.
In view of the above, it is an object of the present invention to provide two IC chips from which the entire Batcher- banyan network can be implemented. It is a further object of the invention to implement the Batcher-banyan network using adjacnt horizontal and vertical stacks of these chips so as to minimize signal propagation delays within the network.